/*
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct TreeNode
{
	int data;
	struct TreeNode* lchild;
	struct TreeNode* rchild;
}TreeNode;
typedef struct QueueNode
{
	TreeNode* node;
	struct QueueNode* pre;
	struct QueueNode* next;
};
void creatTree(TreeNode** t,int* index,char* data)
{
	char ch;
	ch = data[*index];
	(*index)++;
	if (ch == '#')
		*t = NULL;
	else
	{
		*t = (TreeNode*)malloc(sizeof(TreeNode));
		assert(*t);
		(*t)->data = ch;
		creatTree(&((*t)->lchild), index, data);
		creatTree(&((*t)->rchild), index, data);
	}
}
void preOrder(TreeNode* t)
{
	if (t == NULL)
		return;
	else
	{
		printf("%c", t->data);
		preOrder(t->lchild);
		preOrder(t->rchild);
	}
}
QueueNode* initQueue()
{
	QueueNode* Q = (QueueNode*)malloc(sizeof(QueueNode));
	assert(Q);
	Q->node = NULL;
	Q->next =Q;
	Q->pre = Q;
	return Q;
}
void enQueue(QueueNode* Q,TreeNode* data)
{
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->node = data;
	newnode->pre= Q;
	newnode->next = Q;
	Q->pre->next = newnode;
	Q->pre = newnode;
}
int is_emepty(QueueNode* Q)
{
	if (Q->next == NULL)
		return 0;
	else
		return 1;
}
QueueNode* deQueue(QueueNode* Q)
{
	if (is_emepty(Q) == 0)
		return NULL;
	else
	{
		QueueNode* node = Q->next;
		Q->next->next->pre = Q;
		Q->next = Q->next->next;
		return node;
	}
}
void levelTraverse(QueueNode* Q, TreeNode* T)
{
	enQueue(Q, T);
	while (is_emepty(Q))
	{
		QueueNode* node = deQueue(Q);
		printf("%c ", node->node->data);
		if (node->node->lchild)
			enQueue(Q, node->node->lchild);
		if (node->node->rchild)
			enQueue(Q, node->node->rchild);
	}
}
int main()
{
	TreeNode* t;
	char data[100];
	int index = 0;
	gets_s(data);
	creatTree(&t, &index, data);
	preOrder(t);
	printf("\n");
	QueueNode* q = initQueue();
	levelTraverse(q, t);
	return 0;
}
*/
